Search for: All records

A Boolean {\em $$k$$-monotone} function defined over a finite poset domain $${\cal D}$$ alternates between the values $$0$$ and $$1$$ at most $$k$$ times on any ascending chain in $${\cal D}$$. Therefore, $$k$$-monotone functions are natural generalizations of the classical {\em monotone} functions, which are the {\em $$1$$-monotone} functions. Motivated by the recent interest in $$k$$-monotone functions in the context of circuit complexity and learning theory, and by the central role that monotonicity testing plays in the context of property testing, we initiate a systematic study of $$k$$-monotone functions, in the property testing model. In this model, the goal is to distinguish functions that are $$k$$-monotone (or are close to being $$k$$-monotone) from functions that are far from being $$k$$-monotone. Our results include the following: \begin{enumerate} \item We demonstrate a separation between testing $$k$$-monotonicity and testing monotonicity, on the hypercube domain $$\{0,1\}^d$$, for $$k\geq 3$$; \item We demonstrate a separation between testing and learning on $$\{0,1\}^d$$, for $$k=\omega(\log d)$$: testing $$k$$-monotonicity can be performed with $$2^{O(\sqrt d \cdot \log d\cdot \log{1/\eps})}$$ queries, while learning $$k$$-monotone functions requires $$2^{\Omega(k\cdot \sqrt d\cdot{1/\eps})}$$ queries (Blais et al. (RANDOM 2015)). \item We present a tolerant test for functions $$f\colon[n]^d\to \{0,1\}$$ with complexity independent of $$n$$, which makes progress on a problem left open by Berman et al. (STOC 2014). \end{enumerate} Our techniques exploit the testing-by-learning paradigm, use novel applications of Fourier analysis on the grid $$[n]^d$, and draw connections to distribution testing techniques.